from collections import defaultdict


class Solution:
    """
    方法： minWindow

    逻辑: 使用滑动窗口技术遍历字符串s，统计每个单词的出现次数，并检查是否所有单词都在窗口内出现了指定次数。

    Args:
        s (str): 输入字符串。
        t (str): 目标字符串，用于比较字母出现次数。

    Returns:
        str: 返回最小窗口子串。

    Time: O(m+n) 或 O(m+n+∣Σ∣)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣=128。注意 left 只会增加不会减少，
    二重循环的时间复杂度为 O(m)。使用哈希表写法的时间复杂度为 O(m+n)，数组写法的时间复杂度为 O(m+n+∣Σ∣)。

    Space: O(∣Σ∣)。无论 m 和 n 有多大，额外空间都不会超过 O(∣Σ∣)。
    """
    def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)
        cnt = defaultdict(int)
        for c in t:
            cnt[c] += 1
        less = len(cnt)
        left = 0
        for right, c in enumerate(s):
            cnt[c] -= 1 #右端点字母移入子串
            if cnt[c] == 0:
                # 窗口中字母 c 出现次数和 t 中一致 
                less -= 1
            while less == 0: # 窗口中所有字母都已经出现
                if right - left < ans_right - ans_left: #更新窗口位置
                    ans_left, ans_right = left, right
                x = s[left]  # 最左边字母
                if cnt[x] == 0:
                    less += 1
                cnt[x] += 1
                left += 1
        return "" if ans_left < 0 else s[ans_left: ans_right + 1]